public class BinarySearchTree {
	private Node root;
	private Node cur;

	public BinarySearchTree() {
		cur = null;
		root = null;
	}

	public BinarySearchTree(char value) {
		Node tree = new Node(value);
		cur = tree;
		root = tree;
	}

	public char getCurValue() {
		return this.cur.getValue();
	}

	public boolean setCurLeft() {
		if (cur.getLeft() != null) {
			this.cur = this.cur.getLeft();
			return true;
		}
		return false;
	}

	public boolean setCurRight() {
		if (cur.getRight() != null) {
			this.cur = this.cur.getRight();
			return true;
		}
		return false;
	}

	public boolean setCurParent() {
		if (cur.getParent() != null) {
			this.cur = this.cur.getParent();
			return true;
		}
		return false;
	}

	public void setCurRoot() {
		this.cur = this.root;
	}

	public int deep() {
		if (cur == null) {
			return 0;
		} else {
			if (deep(cur.getLeft()) > deep(cur.getRight())) {
				return deep(cur.getLeft()) + 1;
			} else {
				return deep(cur.getRight()) + 1;
			}
		}
	}

	private int deep(Node node) {

		if (node == null) {
			return 0;
		} else {
			if (deep(node.getLeft()) > deep(node.getRight())) {
				return deep(node.getLeft()) + 1;
			} else {
				return deep(node.getRight()) + 1;
			}
		}
	}

	public void add(char value) {
		Node tree = new Node(value);
		if (root == null) {
			cur = tree;
			root = tree;
			return;
		}
		cur = root;
		while (true) {
			if (cur.getValue() == value) {
				return;
			}
			if (cur.getValue() > value) {
				if (cur.getLeft() == null) {
					tree.setParent(cur);
					cur.setLeft(tree);
				} else
					cur = cur.getLeft();
			} else {
				if (cur.getValue() < value) {
					if (cur.getRight() == null) {
						tree.setParent(cur);
						cur.setRight(tree);
					} else
						cur = cur.getRight();
				}
			}
		}

	}

	public boolean search(char value) {
		cur = root;

		while (true) {
			if (cur == null) {
				cur = root;
				return false;
			}
			if (cur.getValue() == value) {
				return true;
			}

			if (value > cur.getValue()) {
				cur = cur.getRight();
			} else {
				if (value < cur.getValue())
					cur = cur.getLeft();
			}
		}
	}

	public boolean deleteNode(char value) {
		while (true) {
			if (this.search(value)) {
				if (cur.getRight() == null) {
					if (cur.getParent().getValue() > cur.getValue()) {
						cur.getParent().setLeft(cur.getLeft());
						if (cur.getLeft() != null) {
							cur.getLeft().setParent(cur.getParent());
						}
						return true;
					} else {
						cur.getParent().setRight(cur.getLeft());
						if (cur.getLeft() != null) {
							cur.getLeft().setParent(cur.getParent());
						}
						return true;
					}
				} else {
					this.turn();
				}
			} else
				return false;
		}
	}

	public void turn() {
		Node parent = cur.getParent();
		Node right = cur.getRight();
		Node node = right.getLeft();
		
		cur.setRight(node);
		right.setLeft(cur);
		
		if(node!=null){
			node.setParent(cur);
		}
		cur.setParent(right);
		
		if (parent != null) {
			if (parent.getValue() > right.getValue()) {
				parent.setLeft(right);
				right.setParent(parent);
			} else {
				parent.setRight(right);
				right.setParent(parent);
			}
		} else {
			right.setParent(null);
			root = right;
			cur = root;
		}
		
	}

	void clearBST() {
		root = null;
		cur = null;
	}
}
